#include <iostream>
#include <list>
#include <unordered_map>
#include <memory>

using namespace std;

struct FreqNode;
//using FreqList = list<FreqNode, Allocator<FreqList>>;
using FreqList = list<FreqNode>;

struct DataNode {
    int key_;
    int val_;
    FreqList::iterator iterpos_;
    DataNode(int key, int val, FreqList::iterator pos = FreqList::iterator())
        : key_(key)
        , val_(val)
        , iterpos_(pos)
    {}
};

//using DataNodeList = list<DataNode, Allocator<DataNode>>;
using DataNodeList = list<DataNode>;

struct FreqNode {
    int frequency_;
    DataNodeList nodeList_;
    FreqNode(int c = 0)
        : frequency_(c)
    {}
};

class LFUCache
{
public:
    LFUCache(int cap)
        : capacity_(cap)
    {}
    ~LFUCache() = default;
    LFUCache(const LFUCache &) = delete;
    LFUCache &operator=(const LFUCache &) = delete;

public:
    void put(int key, int val)
    {
        if (capacity_ == 0)
        {
            return ;
        }
        auto pos = router_.find(key);
        if (pos != router_.end())
        {
            pos->second->val_ = val;
            updateCache(key);
        }
        else
        {
            if (router_.size() == capacity_)
            {
                popCache();
            }
            if (cache_.empty() || cache_.back().frequency_ != 1)
            {
                cache_.push_back(FreqNode(1));
            }
            auto it = --cache_.end();
            it->nodeList_.push_front(DataNode(key, val, it));
            router_.emplace(key, it->nodeList_.begin());
        }
    }

    int get(int key)
    {
        auto pos = router_.find(key);
        if (pos == router_.end())
        {
            return -1;
        }
        int val = pos->second->val_;
        updateCache(key);
        return val;
    }

private:
    void updateCache(int key)
    {
        auto pos = router_.find(key);
        auto it = pos->second;
        if (it->iterpos_ == cache_.begin())
        {
            cache_.push_front(FreqNode(it->iterpos_->frequency_ + 1));
        }
        else
        {
            FreqList::iterator pre = it->iterpos_; --pre;
            if (pre->frequency_ != it->iterpos_->frequency_ + 1)
            {
                cache_.emplace(it->iterpos_, FreqNode(it->iterpos_->frequency_ + 1));
            }
        }
        auto cur = it->iterpos_;
        auto pre = it->iterpos_; --pre;
        pre->nodeList_.push_front(DataNode(key, it->val_, pre));
        cur->nodeList_.erase(it);
        pos->second = pre->nodeList_.begin();
    }
    void popCache()
    {
        for (auto it = --cache_.end();;)
        {

        }
        auto it = --cache_.end();
        do {
            if (it->nodeList_.empty())
            {
                cache_.erase(it--);
                continue;
            }
            auto out = it->nodeList_.back();
            router_.erase(out.key_);
            it->nodeList_.pop_back();
            break;
        } while (1);
    }

private:
    size_t capacity_;
    FreqList cache_; //一个存放不同频率DataNodeList的节点
    unordered_map<int, DataNodeList::iterator> router_; //每个key与其对应的在DataNodeList上所在位置的iterator之间的映射关系
};

int main(int argc, const char** argv) {
    LFUCache lfu(3);
    lfu.put(1, 1);
    lfu.put(2, 2);
    lfu.put(3, 3);
    cout << lfu.get(1) << endl;
    cout << lfu.get(2) << endl;
    cout << lfu.get(1) << endl;
    cout << lfu.get(2) << endl;
    cout << lfu.get(1) << endl;
    cout << lfu.get(2) << endl;
    cout << lfu.get(1) << endl;
    cout << lfu.get(2) << endl;
    cout << lfu.get(3) << endl;
    return 0;
}